

//快速乘

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static long multiplyMod(long a, long b, long p) {
        long result = 0;
        a = a % p;
        while (b > 0) {
            if (b % 2 == 1) {
                result = (result + a) % p;
            }
            a = (2 * a) % p;
            b /= 2;
        }
        return result;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 读取询问次数
        int q = sc.nextInt();
        // 处理每次询问
        for (int i = 0; i < q; i++) {
            long a = sc.nextLong();
            long b = sc.nextLong();
            long p = sc.nextLong();

            // 输出结果
            System.out.println(multiplyMod(a, b, p));
        }

        sc.close();
    }
}